
import java.util.Arrays;

// 在数组对项基础上，继续封装出顺序表对象
// 将 Long.MIN_VALUE 假定为无效值
/*
对象具备的一致性问题：
1) size <= array.length
2) 真正有用的元素的下标 [0, size)
3) 要插入新的元素，由于顺序不允许出现空洞，可选的下标范围 [0, size]
4) [size, array.length) 都应该是无效的元素(Long.MIN_VALUE)
 */
public class MyArrayList {
    private long[] array;   // 1) 存元素的空间   2) 空间的容量
    private int size;       // 元素的个数

    public MyArrayList() {
        array = new long[2];
        size = 0;
        // 这一步理论上不是必须的
        Arrays.fill(array, Long.MIN_VALUE);
    }

    /*
    方法元素
    指定位置进行放入
    在最后插入元素：尾插操作 （pushBack）
     */

    // 最好: O(1)
    // 平均: O(1)
    // 最坏: O(n)
    // 尾插操作
    public void add(long e) {
        ensureCapacity();

        // 1. 将元素放在 [size] 下标处
        array[size] = e;
        // 2. 让 size++
        size++;
    }

    // 最好: O(1)
    // 平均: O(1)
    // 最坏: O(n)
    // 确保至少可以放一个元素
    private void ensureCapacity() {
        if (size < array.length) {
            return;
        }

        // 一定放不下了，进行扩容
        // 搬家
        // 1. 找到新房子 —— 定义一个新的数组对象
        //    1) 新数组长度是多少？ 至少是 array.length + 1
        //    2) 一般扩容成原来的 1.5 到 2 倍


        int newLength = array.length * 2;
        long[] newArray = Arrays.copyOf(array, newLength);
//        long[] newArray = new long[newLength];
//
//        // 2. 搬东西
//        for (int i = 0; i < size; i++) {
//            newArray[i] = array[i];
//        }
        //System.arraycopy(array, 0, newArray, 0, size);
        // 把 [size, newLength) 设置成无效值
        Arrays.fill(newArray, size, newLength, Long.MIN_VALUE);

        array = newArray;
    }

    // O(1)
    // 返回元素个数
    // 这样处理
    // 外部只能看元素个数，但改不了元素个数
    public int size() {
        return size;
    }

    // O(1)
    // 返回 index 位置的元素
    public long get(int index) {
        // 1. 检查下标合法性 0 <= index < size
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException(index + ": " + size);
        }

        return array[index];
    }

    // 检查对象的正确性
    // 对象不正确了，就抛异常
    public void check() {
        if (array == null) {
            throw new RuntimeException();
        }
        if (array.length == 0) {
            throw new RuntimeException();
        }
        if (size < 0) {
            throw new RuntimeException();
        }
        if (size > array.length) {
            throw new RuntimeException();
        }
        // [0, size) 是有效元素 (不是 Long.MIN_VALUE)
        for (int i = 0; i < size; i++) {
            if (array[i] == Long.MIN_VALUE) {
                throw new RuntimeException();
            }
        }
        // [size, array.length) 都是无效值（是 Long.MIN_VALUE）
        for (int i = size; i < array.length; i++) {
            if (array[i] != Long.MIN_VALUE) {
                throw new RuntimeException();
            }
        }
    }

    public void add(int index, long e) {
        // 下标的合法性: 0 <= index <= size
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException(index + ": " + size);
        }

        ensureCapacity(); // 扩容检查
        // TODO:
        for(int i = this.size; i > index; i--){
            array[i] = array[i-1];
        }
        size++;
        array[index] = e;
        return ;
    }




    public void remove(int index){
        if(index < 0 || index > size){
            throw new RuntimeException("非法下标");
        }

        // 删除的位置 覆盖到
        for(int i = index + 1 ; i < size ; i++){
            array[i-1] = array[i];
        }
        array[--size] = Long.MIN_VALUE;
        return ;
    }
}
